<!DOCTYPE HTML>
<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="chrome=1">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no">

    

    <title>HashMap的实现原理 | 程序员Sherwin</title>
    <meta name="author" content="Sherwin Wei">
    
    <meta name="description" content="1.HashMap概述： &amp;emsp; &amp;emsp; HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
2.HashMap的数据结构： &amp;emsp;&amp;emsp;  在java编程语">
    

   
   <meta name="keywords" content="HashMap原理,java基础,魏远标,Sherwin,java程序员,程序员Sherwin,程序员魏远标">
   
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">

    <meta property="og:title" content="HashMap的实现原理"/>
    <meta property="og:site_name" content="程序员Sherwin"/>

    
    <meta property="og:image" content=""/>
    

    <link rel="icon" type="image/png" href="/favicon.png">
    <link rel="alternate" href="/atom.xml" title="程序员Sherwin" type="application/atom+xml">
    <link rel="stylesheet" href="/css/lib/materialize.min.css">
    <link rel="stylesheet" href="/css/lib/font-awesome.min.css">
    <link rel="stylesheet" href="/css/style.css" media="screen" type="text/css">

    
        <link rel="stylesheet" href="/css/lib/prettify-tomorrow-night-eighties.css" type="text/css">
    
    <!--[if lt IE 9]><script src="//html5shiv.googlecode.com/svn/trunk/html5.js"></script><![endif]-->
</head>


<body>
    <img src="/weixin_favicon.png" style="position: absolute; left: -9999px; opacity: 0; filter: alpha(opacity=0);">

    <nav class="indigo">
    <div class="nav-wrapper">
        <a href="#" data-activates="main-menu" class="button-collapse">
            <i class="fa fa-navicon"></i>
        </a>
        <div class="">
            <a href="/" class="brand-logo hide-on-med-and-down">程序员Sherwin</a>
            <ul class="right hide-on-med-and-down">
                
                    <li>
                        <a class="menu-home " href="/" >
                            <i class="fa fa-home "></i>
                            
                            首页
                        </a>
                    </li>
                
                    <li>
                        <a class="menu-archive " href="/archives" >
                            <i class="fa fa-archive "></i>
                            
                            归档
                        </a>
                    </li>
                
                    <li>
                        <a class="menu-category category-menu" href="javascript:;" data-activates="category-menu" >
                            <i class="fa fa-bookmark "></i>
                            
                            分类
                        </a>
                    </li>
                
                    <li>
                        <a class="menu-reading " href="/reading" >
                            <i class="fa fa-book "></i>
                            
                            读书
                        </a>
                    </li>
                
                    <li>
                        <a class="menu-about " href="/about" >
                            <i class="fa fa-user "></i>
                            
                            关于
                        </a>
                    </li>
                
                    <li>
                        <a class="menu-search modal-trigger " href="#search" >
                            <i class="fa fa-search "></i>
                            
                            搜索
                        </a>
                    </li>
                
            </ul>
            <div>
    <ul class="side-nav indigo darken-1" id="main-menu">
        
        <li class="side-user">
            <div class="row">
                <div class="col s4 no-padding">
                    <img class="avatar-image circle responsive-img" src="http://p5zbw6dku.bkt.clouddn.com/18-3-27/79800938.jpg" alt="User Avatar">
                </div>
                <div class="info col s8 valign-wrapper no-padding">
                    <div class="valign">
                        <p class="name">魏远标</p>
                        <p class="desc">Java后端/全栈</p>
                    </div>
                </div>
            </div>
        </li>
        

        
            <li class="no-padding">
                <a class="waves-effect menu-home " href="/" >
                    <i class="fa fa-home "></i>
                    
                    首页
                </a>
            </li>
        
            <li class="no-padding">
                <a class="waves-effect menu-archive " href="/archives" >
                    <i class="fa fa-archive "></i>
                    
                    归档
                </a>
            </li>
        
            <li class="no-padding">
                <a class="waves-effect menu-category category-menu" href="javascript:;" data-activates="category-menu" >
                    <i class="fa fa-bookmark "></i>
                    
                    分类
                </a>
            </li>
        
            <li class="no-padding">
                <a class="waves-effect menu-reading " href="/reading" >
                    <i class="fa fa-book "></i>
                    
                    读书
                </a>
            </li>
        
            <li class="no-padding">
                <a class="waves-effect menu-about " href="/about" >
                    <i class="fa fa-user "></i>
                    
                    关于
                </a>
            </li>
        
            <li class="no-padding">
                <a class="waves-effect menu-search modal-trigger " href="#search" >
                    <i class="fa fa-search "></i>
                    
                    搜索
                </a>
            </li>
        
    </ul>

    <ul class="side-nav indigo darken-1" id="category-menu">
    

            

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/java/">
                    java <span class="right">12 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/linux/">
                    linux <span class="right">2 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/web前端/">
                    web前端 <span class="right">1 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/生活/">
                    生活 <span class="right">7 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/网络/">
                    网络 <span class="right">1 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/java面试/">
                    java面试 <span class="right">3 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/juc/">
                    juc <span class="right">1 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/jvm/">
                    jvm <span class="right">2 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/mybatis/">
                    mybatis <span class="right">1 篇</span></a>
                </a>
            </li>

        

            <li class="collapse-level-0" collapse-level="0">
                <a class="no-padding" href="/categories/spring/">
                    spring <span class="right">1 篇</span></a>
                </a>
            </li>

        

    </ul>
</div>

        </div>
    </div>
</nav>

<div id="search" class="modal search-modal">
    <div class="row">
        <div class="input-field col s12">
              <input id="search-input" type="text">
              <label for="search-input">搜索</label>
        </div>

    </div>
    <div id="search-result" class="search-result col s12">

    </div>
</div>


    <main>
        <div class="container main-container">
    <nav class="page-nav hide-on-small-only">
    <div class="nav-wrapper indigo">
        <span class="breadcrumb">当前位置（分类目录）</span>
        
            
    
    
    <a class="breadcrumb" href="/categories/java/">java</a>


        

        
    </div>
</nav>

<article>
    <div class="card">
        <div class="card-content">
            

            <div class="article-title">
                
    
        <h1>HashMap的实现原理</h1>
    


            </div>
            <time class="pink-link-context" datetime="2018-06-01T01:37:25.000Z"><a href="/java/2.HashMap的实现原理/">2018-06-01</a></time>

            <span id="busuanzi_container_page_pv" class="read-times-container">
    <i class="fa fa-eye"></i>
    <span id="busuanzi_value_page_pv"></span>
</span>

            
    <div class="tags-row">
        
            <a href="/tags/java基础/" class="chip pink lighten-1">java基础</a>
        
    </div>


            <div class="toc pink-link-context hide-on-med-and-down">
    <ol class="section table-of-contents"><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#1-HashMap概述："><span class="section table-of-contents-text">1.HashMap概述：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#2-HashMap的数据结构："><span class="section table-of-contents-text">2.HashMap的数据结构：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#3-HashMap的存取实现："><span class="section table-of-contents-text">3.HashMap的存取实现：</span></a><ol class="section table-of-contents-child"><li class="section table-of-contents-item section table-of-contents-level-4"><a class="section table-of-contents-link" href="#1-存储："><span class="section table-of-contents-text">1) 存储：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-4"><a class="section table-of-contents-link" href="#2-读取："><span class="section table-of-contents-text">2) 读取：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-4"><a class="section table-of-contents-link" href="#3-归纳起来简单地说"><span class="section table-of-contents-text">3) 归纳起来简单地说</span></a></li></ol></li><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#4-HashMap的resize（rehash）："><span class="section table-of-contents-text">4.HashMap的resize（rehash）：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#5-HashMap的性能参数："><span class="section table-of-contents-text">5.HashMap的性能参数：</span></a></li><li class="section table-of-contents-item section table-of-contents-level-3"><a class="section table-of-contents-link" href="#6-Fail-Fast机制："><span class="section table-of-contents-text">6.Fail-Fast机制：</span></a></li></ol>
</div>


            <div class="entry pink-link-context">
                <h3 id="1-HashMap概述："><a href="#1-HashMap概述：" class="headerlink" title="1.HashMap概述："></a>1.HashMap概述：</h3><p> &emsp; &emsp; HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。</p>
<h3 id="2-HashMap的数据结构："><a href="#2-HashMap的数据结构：" class="headerlink" title="2.HashMap的数据结构："></a>2.HashMap的数据结构：</h3><p> &emsp;&emsp;  在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。</p>
<p> <img src="http://p5zbw6dku.bkt.clouddn.com/18-3-22/3994350.jpg" alt="image"></p>
<p>   从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。<br>   源码如下：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/** </span></span><br><span class="line"><span class="comment"> * The table, resized as necessary. Length MUST Always be a power of two. </span></span><br><span class="line"><span class="comment"> */</span>  </span><br><span class="line"><span class="keyword">transient</span> Entry[] table;  </span><br><span class="line">  </span><br><span class="line"><span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; <span class="keyword">implements</span> <span class="title">Map</span>.<span class="title">Entry</span>&lt;<span class="title">K</span>,<span class="title">V</span>&gt; </span>&#123;  </span><br><span class="line"><span class="keyword">final</span> K key;  </span><br><span class="line">V value;  </span><br><span class="line">Entry&lt;K,V&gt; next;  </span><br><span class="line"><span class="keyword">final</span> <span class="keyword">int</span> hash;  </span><br><span class="line">……  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>&emsp;&emsp;可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。</p>
<h3 id="3-HashMap的存取实现："><a href="#3-HashMap的存取实现：" class="headerlink" title="3.HashMap的存取实现："></a>3.HashMap的存取实现：</h3><h4 id="1-存储："><a href="#1-存储：" class="headerlink" title="1) 存储："></a>1) 存储：</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;  </span><br><span class="line"><span class="comment">// HashMap允许存放null键和null值。  </span></span><br><span class="line"><span class="comment">// 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  </span></span><br><span class="line"><span class="keyword">if</span> (key == <span class="keyword">null</span>)  </span><br><span class="line"><span class="keyword">return</span> putForNullKey(value);  </span><br><span class="line"><span class="comment">// 根据key的keyCode重新计算hash值。  </span></span><br><span class="line"><span class="keyword">int</span> hash = hash(key.hashCode());  </span><br><span class="line"><span class="comment">// 搜索指定hash值在对应table中的索引。  </span></span><br><span class="line"><span class="keyword">int</span> i = indexFor(hash, table.length);  </span><br><span class="line"><span class="comment">// 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  </span></span><br><span class="line"><span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[i]; e != <span class="keyword">null</span>; e = e.next) &#123;  </span><br><span class="line">Object k;  </span><br><span class="line"><span class="keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k))) &#123;  </span><br><span class="line">V oldValue = e.value;  </span><br><span class="line">e.value = value;  </span><br><span class="line">e.recordAccess(<span class="keyword">this</span>);  </span><br><span class="line"><span class="keyword">return</span> oldValue;  </span><br><span class="line">&#125;  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="comment">// 如果i索引处的Entry为null，表明此处还没有Entry。  </span></span><br><span class="line">modCount++;  </span><br><span class="line"><span class="comment">// 将key、value添加到i索引处。  </span></span><br><span class="line">addEntry(hash, key, value, i);  </span><br><span class="line"><span class="keyword">return</span> <span class="keyword">null</span>;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;&emsp;从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。</p>
<p> &emsp;&emsp;  addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法，代码如下：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">void addEntry(int hash, K key, V value, int bucketIndex) &#123;  </span><br><span class="line">// 获取指定 bucketIndex 索引处的 Entry   </span><br><span class="line">Entry&lt;K,V&gt; e = table[bucketIndex];  </span><br><span class="line">// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  </span><br><span class="line">table[bucketIndex] = new Entry&lt;K,V&gt;(hash, key, value, e);  </span><br><span class="line">// 如果 Map 中的 key-value 对的数量超过了极限  </span><br><span class="line">if (size++ &gt;= threshold)  </span><br><span class="line">// 把 table 对象的长度扩充到原来的2倍。  </span><br><span class="line">resize(2 * table.length);  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p> &emsp;&emsp; 当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。</p>
<p> &emsp;&emsp;  hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">hash</span><span class="params">(<span class="keyword">int</span> h)</span> </span>&#123;  </span><br><span class="line">h ^= (h &gt;&gt;&gt; <span class="number">20</span>) ^ (h &gt;&gt;&gt; <span class="number">12</span>);  </span><br><span class="line"><span class="keyword">return</span> h ^ (h &gt;&gt;&gt; <span class="number">7</span>) ^ (h &gt;&gt;&gt; <span class="number">4</span>);  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>&emsp;&emsp; 我们可以看到在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的 元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。</p>
<p>&emsp;&emsp; 对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">static</span> <span class="keyword">int</span> <span class="title">indexFor</span><span class="params">(<span class="keyword">int</span> h, <span class="keyword">int</span> length)</span> </span>&#123;  </span><br><span class="line"><span class="keyword">return</span> h &amp; (length-<span class="number">1</span>);  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>&emsp;&emsp;这个方法非常巧妙，它通过 h &amp; (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方，这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码：<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> capacity = <span class="number">1</span>;  </span><br><span class="line"><span class="keyword">while</span> (capacity &lt; initialCapacity)  </span><br><span class="line">capacity &lt;&lt;= <span class="number">1</span>;</span><br></pre></td></tr></table></figure></p>
<p>   这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。<br>当length总是 2 的n次方时，h&amp; (length-1)运算等价于对length取模，也就是h%length，但是&amp;比%具有更高的效率。<br>   这看上去很简单，其实比较有玄机的，我们举个例子来说明：<br>   假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&amp;运算后的结果如下：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">h &amp; (table.length-1) hash table.length-1</span><br><span class="line">8 &amp; (15-1)： 0100   &amp;  1110   =0100</span><br><span class="line">9 &amp; (15-1)： 0101   &amp;  1110   =0100</span><br><span class="line">-----------------------------------------------------------------------------------------------------------------------</span><br><span class="line">8 &amp; (16-1)： 0100   &amp;  1111   =0100</span><br><span class="line">9 &amp; (16-1)： 0101   &amp;  1111   =0101</span><br></pre></td></tr></table></figure></p>
<p> &emsp;&emsp;  从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链 表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么 最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&amp;时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。</p>
<p> &emsp;&emsp;  所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。</p>
<p> &emsp;&emsp;  根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。</p>
<h4 id="2-读取："><a href="#2-读取：" class="headerlink" title="2) 读取："></a>2) 读取：</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(Object key)</span> </span>&#123;  </span><br><span class="line"><span class="keyword">if</span> (key == <span class="keyword">null</span>)  </span><br><span class="line"><span class="keyword">return</span> getForNullKey();  </span><br><span class="line"><span class="keyword">int</span> hash = hash(key.hashCode());  </span><br><span class="line"><span class="keyword">for</span> (Entry&lt;K,V&gt; e = table[indexFor(hash, table.length)];  </span><br><span class="line">e != <span class="keyword">null</span>;  </span><br><span class="line">e = e.next) &#123;  </span><br><span class="line">Object k;  </span><br><span class="line"><span class="keyword">if</span> (e.hash == hash &amp;&amp; ((k = e.key) == key || key.equals(k)))  </span><br><span class="line"><span class="keyword">return</span> e.value;  </span><br><span class="line">&#125;  </span><br><span class="line"><span class="keyword">return</span> <span class="keyword">null</span>;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>&emsp;&emsp;   有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。</p>
<h4 id="3-归纳起来简单地说"><a href="#3-归纳起来简单地说" class="headerlink" title="3) 归纳起来简单地说"></a>3) 归纳起来简单地说</h4><p>&emsp;&emsp; HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。</p>
<h3 id="4-HashMap的resize（rehash）："><a href="#4-HashMap的resize（rehash）：" class="headerlink" title="4.HashMap的resize（rehash）："></a>4.HashMap的resize（rehash）：</h3><p> &emsp;&emsp;  当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。</p>
<p> &emsp;&emsp;  那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小<em>loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16</em>0.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。</p>
<h3 id="5-HashMap的性能参数："><a href="#5-HashMap的性能参数：" class="headerlink" title="5.HashMap的性能参数："></a>5.HashMap的性能参数：</h3><ul>
<li><p>HashMap 包含如下几个构造器：</p>
</li>
<li><p>HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。</p>
</li>
<li>HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。</li>
<li>HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。</li>
<li>HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。</li>
<li>initialCapacity：HashMap的最大容量，即为底层数组的长度。</li>
<li><p>loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。<br>负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。<br>&emsp;&emsp; HashMap的实现中，通过threshold字段来判断HashMap的最大容量：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">threshold = (<span class="keyword">int</span>)(capacity * loadFactor);</span><br></pre></td></tr></table></figure>
<p>&emsp;&emsp;<br>结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：</p>
</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (size++ &gt;= threshold) </span><br><span class="line">resize(<span class="number">2</span> * table.length);</span><br></pre></td></tr></table></figure>
<h3 id="6-Fail-Fast机制："><a href="#6-Fail-Fast机制：" class="headerlink" title="6.Fail-Fast机制："></a>6.Fail-Fast机制：</h3><p>&emsp;&emsp;我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。</p>
<p>&emsp;&emsp;这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">HashIterator() &#123;  </span><br><span class="line">expectedModCount = modCount;  </span><br><span class="line">if (size &gt; 0) &#123; // advance to first entry  </span><br><span class="line">Entry[] t = table;  </span><br><span class="line">while (index &lt; t.length &amp;&amp; (next = t[index++]) == null)  </span><br><span class="line">;  </span><br><span class="line">&#125;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>&emsp;&emsp;在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：</p>
<ul>
<li><p>注意到modCount声明为volatile，保证线程之间修改的可见性。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">final Entry&lt;K,V&gt; nextEntry() &#123; </span><br><span class="line">if (modCount != expectedModCount) </span><br><span class="line">throw new ConcurrentModificationException();</span><br></pre></td></tr></table></figure>
<ul>
<li>在HashMap的API中指出：<br>&emsp;&emsp;由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。</li>
<li>注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。</li>
</ul>
</li>
</ul>

                
<p class="pink-link-context">
    <a href="/java/3.LinkedHashMap的实现原理/" rel="next" title="LinkedHashMap的实现原理">
    上一篇：LinkedHashMap的实现原理
  </a>
</p>



<p class="pink-link-context">
    <a href="/java/1.ArrayList的实现原理/" rel="next" title="ArrayList的实现原理">
    下一篇：ArrayList的实现原理
  </a>
</p>


            </div>
			
        </div>
    </div>
</article>




    <section id="comments">
        <!--高速版，加载速度快，使用前需测试页面的兼容性-->
        <div id="SOHUCS" sid="HashMap的实现原理"></div>
        <script>
          (function(){
            var appid = 'cytwu2Jh8',
            conf = 'prod_f36aa8fb3548cb02167fd6c482acf807';
            var doc = document,
            s = doc.createElement('script'),
            h = doc.getElementsByTagName('head')[0] || doc.head || doc.documentElement;
            s.type = 'text/javascript';
            s.charset = 'utf-8';
            s.src =  'http://assets.changyan.sohu.com/upload/changyan.js?conf='+ conf +'&appid=' + appid;
            h.insertBefore(s,h.firstChild);
            window.SCS_NO_IFRAME = true;
          })()
        </script>    
    </section>





</div>

        <div class="fixed-action-btn float-sitemap">
    <a class="btn-floating btn-large pink">
      <i class="fa fa-caret-square-o-up"></i>
    </a>
    <ul>
      <li><a class="btn-return-top btn-floating waves-effect green" title="回到顶部"><i class="fa fa-arrow-circle-o-up"></i></a></li>
      <li><a class="btn-floating waves-effect button-collapse yellow darken-1"  data-activates="main-menu" title="菜单"><i class="fa fa-navicon"></i></a></li>
    </ul>
  </div>

    </main>
    <footer class="page-footer indigo darken-1">
    
    <div class="footer-container container">
        <div class="row">
            
            <div class="social-group col m4 s12">
                <h5 class="white-text">社交</h5>
                
                    <a class="social-link" href="https://weibo.com/1903200010" target="_blank">
                        <i class="fa fa-2x fa-weibo"></i>
                    </a>
                
                    <a class="social-link" href="https://github.com/sherwin28" target="_blank">
                        <i class="fa fa-2x fa-github"></i>
                    </a>
                
                    <a class="social-link" href="/atom.xml" target="_blank">
                        <i class="fa fa-2x fa-rss"></i>
                    </a>
                
                
     <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    <div class="site-visitors-container white-text">
        <span>
            <i class="fa fa-user"></i>
            <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
        </span>
        <span>&nbsp;|&nbsp;</span>
        <span>
            <i class="fa fa-eye"></i>
            <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
        </span>
    </div>


            </div>
            

            
            <div class="col m8 s12">
                <h5 class="white-text">友情链接</h5>
                
                    <a class="social-link" href="http://blog.didispace.com/" target="_blank">程序猿DD</a>
                
                    <a class="social-link" href="https://springcloud.cc/" target="_blank">Spring Cloud中文网</a>
                
                    <a class="social-link" href="http://itmuch.com/" target="_blank">周立|Spring Cloud </a>
                
            </div>
            
        </div>
    </div>
    

    <div class="footer-copyright pink-link-context">
        <div class="container">
            © 2018 weiyuanbiao.cn, All rights reserved.
            <a href="http://weiyuanbiao.cn" style="margin-left:10px;">weiyuanbiao.cn</a>
            <a href="http://www.miitbeian.gov.cn" target="_blank" style="margin-left:10px;">粤ICP备15018188号-1</a>
            <!-- 
            <p class="right" style="margin-top: 0;">本博客由 <a href="https://hexo.io">Hexo</a> 强力驱动 | 主题 <a href="https://github.com/raytaylorlin/hexo-theme-raytaylorism">raytaylorism</a></p>
            -->
        </div>
    </div>
</footer>


<noscript>
    <div class="noscript">
        <p class="center-align">当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器</p>
    </div>
</noscript>
<div class="noscript">
    <p class="center-align">当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器</p>
</div>


<script src="/js/jquery.min.js"></script>
<script src="/js/materialize.min.js"></script>

<script>
    (function($) {
        $(document).ready(function() {
            // 隐藏禁用javascript（针对微信内置浏览器）的提示
            $('.noscript').hide();

            // 图片缩放效果
            var $imgs = $('img').not('.slider-image').not('.avatar-image').not('.carousel-image').not('.card-cover-image').not('.qrcode');

            // 给图片加上点击放大效果（materialbox插件）
            $imgs.addClass('materialboxed').each(function(i, el) {
                $(this).attr('data-caption', $(this).attr('alt') || ' ');
            }).materialbox();

            // 优化表格的显示
            $('table').each(function() {
                var $table = $(this);
                // 除去多行代码的情况
                if ($table.find('pre').length == 0) {
                    $table.addClass('responsive-table striped bordered');
                }
            });

            // 首页幻灯片
            $('.slider').slider({indicators: true, full_width: true, interval: 8000});

            $(".button-collapse").sideNav();
            $(".category-menu").sideNav();

            // 针对gallery post
            $('.carousel').carousel({full_width: true});
            $('.carousel-control.prev').click(function() {
                $('.carousel').carousel('prev');
            });
            $('.carousel-control.next').click(function() {
                $('.carousel').carousel('next');
            });

            // 文章目录
            $('article').not('.simple-article').find('h1').add('h2').add('h3').add('h4').add('h5').add('h6').scrollSpy();

            // 目录随屏幕滚动（防止目录过长越过footer）
            var $toc = $('.toc');
            var scrollTargetTop = 0;
            $(window).scroll(function() {
                var $activeLink = $toc.find('a.active.section');
                if ($(window).scrollTop() < 100) {
                    scrollTargetTop = 0;
                } else {
                    if ($activeLink[0]) {
                        scrollTargetTop = $activeLink.offset().top - $toc.offset().top;
                    }
                }
                $toc.css('top', '-' + scrollTargetTop + 'px');
            });

            // 修正文章目录的left-border颜色
            var color = $('.table-of-contents-text').css('color');
            $('.table-of-contents-link').css('border-left-color', color);

            // 针对移动端做的优化：FAB按钮点击一下收回
            if (/Android|webOS|iPhone|iPad|iPod|BlackBerry|IEMobile|Opera Mini/i.test(navigator.userAgent)) {
                $('.fixed-action-btn').addClass('click-to-toggle');
            }
            // 回到顶部
            $('.btn-return-top').click(function() {
                $('body, html').animate({
                    scrollTop: 0
                }, 500);
            });

            // 重置读书页面的Tab标签页的颜色
            $('li.tab a').hover(function() {
                $(this).toggleClass('text-lighten-4');
            });
            $('.indicator').addClass('pink lighten-2');

            
            // 添加new标签
            $('.menu-reading').append('<span class="new badge pink"></span>');
            

            // 搜索功能
            $('.modal-trigger').leanModal({
                // 打开搜索框时自动聚焦
                ready: function() {
                    if ($('#search').is(":visible")) {
                        $('#search-input').focus();
                    }
                }
            });
            var searchXml = "search.xml";
            if (searchXml.length == 0) {
             	searchXml = "search.xml";
            }
            var searchPath = "/" + searchXml;
            initSearch(searchPath, 'search-input', 'search-result');
        });

        // 初始化搜索与匹配函数
        var initSearch = function(path, search_id, content_id) {
            'use strict';
            $.ajax({
                url: path,
                dataType: "xml",
                success: function(xmlResponse) {
                    // get the contents from search data
                    var datas = $("entry", xmlResponse).map(function() {
                        return {
                            title: $("title", this).text(),
                            content: $("content", this).text(),
                            url: $("url", this).text()
                        };
                    }).get();
                    var $input = document.getElementById(search_id);
                    var $resultContent = document.getElementById(content_id);
                    $input.addEventListener('input', function() {
                        var str = '<ul class=\"search-result-list\">';
                        var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                        $resultContent.innerHTML = "";
                        if (this.value.trim().length <= 0) {
                            return;
                        }
                        // perform local searching
                        datas.forEach(function(data) {
                            var isMatch = true;
                            var content_index = [];
                            var data_title = data.title.trim().toLowerCase();
                            var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                            var data_url = data.url;
                            var index_title = -1;
                            var index_content = -1;
                            var first_occur = -1;
                            // only match artiles with not empty titles and contents
                            if (data_title != '' && data_content != '') {
                                keywords.forEach(function(keyword, i) {
                                    index_title = data_title.indexOf(keyword);
                                    index_content = data_content.indexOf(keyword);
                                    if (index_title < 0 && index_content < 0) {
                                        isMatch = false;
                                    } else {
                                        if (index_content < 0) {
                                            index_content = 0;
                                        }
                                        if (i == 0) {
                                            first_occur = index_content;
                                        }
                                    }
                                });
                            }
                            // show search results
                            if (isMatch) {
                                keywords.forEach(function(keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    data_title = data_title.replace(regS, "<span class=\"search-keyword pink lighten-2\">" + keyword + "</span>");
                                });

                                str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                                var content = data.content.trim().replace(/<[^>]+>/g, "");
                                if (first_occur >= 0) {
                                    // cut out 100 characters
                                    var start = first_occur - 20;
                                    var end = first_occur + 80;
                                    if (start < 0) {
                                        start = 0;
                                    }
                                    if (start == 0) {
                                        end = 100;
                                    }
                                    if (end > content.length) {
                                        end = content.length;
                                    }
                                    var match_content = content.substring(start, end);
                                    // highlight all keywords
                                    keywords.forEach(function(keyword) {
                                        var regS = new RegExp(keyword, "gi");
                                        match_content = match_content.replace(regS, "<span class=\"search-keyword pink lighten-2\">" + keyword + "</span>");
                                    });

                                    str += "<p class=\"search-result\">..." + match_content + "...</p>"
                                }
                                str += "</li>";
                            }
                        });
                        str += "</ul>";
                        $resultContent.innerHTML = str;
                    });
                }
            });
        }
    })(jQuery);
</script>


<script src="/js/prettify.js"></script>
<script type="text/javascript">
    $(document).ready(function() {
        $("pre").addClass("prettyprint");
        prettyPrint();
    });
</script>




<script type="text/javascript" src="http://tajs.qq.com/stats?sId=65472120" charset="UTF-8"></script>



<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});
</script>
<script type="text/javascript" async
  src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-MML-AM_CHTML">
</script>





</body>
</html>
